import com.sun.xml.internal.bind.v2.model.core.ID;

import java.time.chrono.IsoChronology;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @ClassName KP18_doubleLinkedListToDeque
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/10/13 15:04
 */
public class KP18_doubleLinkedListToDeque {
    /**
     * 双链表节点
     */
    static class Node<V> {
        public V value;
        public Node<V> prev;
        public Node<V> next;

        public Node(V value) {
            this.prev = null;
            this.next = null;
            this.value = value;
        }
    }

    public static class MyDeque<V> {
        public Node<V> head;
        public Node<V> tail;
        public int size;

        public MyDeque() {
            this.head = null;
            this.tail = null;
            this.size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public int size() {
            return size;
        }

        /**
         * 队头进队
         *
         * @param value
         */
        public void pushHead(V value) {
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                cur.next = head;
                head.prev = cur;
                head = cur;
            }
            size++;
        }

        /**
         * 队尾进队
         *
         * @param value
         */
        public void pushTail(V value) {
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                tail.next = cur;
                cur.prev = tail;
                tail = cur;
            }
            size++;
        }

        /**
         * 队头出队
         *
         * @return
         */
        public V pollHead() {
            V ans = null;
            if (!isEmpty()) {
                size--;
                ans = head.value;
                if (head == tail) {
                    head = null;
                    tail = null;
                } else {
                    head = head.next;
                    head.prev = null;
                }
            }
            return ans;
        }

        /**
         * 队尾出队
         *
         * @return
         */
        public V pollTail() {
            V ans = null;
            if (!isEmpty()) {
                size--;
                ans = tail.value;
                if (head == tail) {
                    head = null;
                    tail = null;
                } else {
                    tail = tail.prev;
                    tail.next = null;
                }
            }
            return ans;
        }

        /**
         * 取队头的元素
         *
         * @return
         */
        public V peekHead() {
            return isEmpty() ? null : head.value;

            //V ans = null;
            //if (!isEmpty()) {
            //    ans = head.value;
            //}
            //return ans;
        }

        /**
         * 取队尾的元素
         *
         * @return
         */
        public V peekTail() {
            return isEmpty() ? null : tail.value;

            //V ans = null;
            //if (!isEmpty()) {
            //    ans = tail.value;
            //}
            //return ans;
        }
    }

    public static void testDeque() {
        MyDeque<Integer> myDeque = new MyDeque<>();
        Deque<Integer> testDeque = new LinkedList<>();
        int testTimes = 100000;
        int maxValue = 1000;
        System.out.println("测试开始！！！");
        for (int i = 0; i < testTimes; i++) {
            if (myDeque.isEmpty() != testDeque.isEmpty()) {
                System.out.println("error1");
            }
            if (myDeque.size() != testDeque.size()) {
                System.out.println("error2");
            }
            Double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * (maxValue + 1));
                if (Math.random() < 0.5) {
                    myDeque.pushHead(num);
                    testDeque.addFirst(num);
                } else {
                    myDeque.pushTail(num);
                    testDeque.addLast(num);
                }
            } else if (decide < 0.66) {
                if (!myDeque.isEmpty()) {
                    int num1 = 0;
                    int num2 = 0;
                    if (Math.random() < 0.5) {
                        num1 = myDeque.pollHead();
                        num2 = testDeque.removeFirst();
                    } else {
                        num1 = myDeque.pollTail();
                        num2 = testDeque.removeLast();
                    }
                    if (num1 != num2) {
                        System.out.println("error3");
                    }
                }
            } else {
                if (!myDeque.isEmpty()) {
                    int num1 = 0;
                    int num2 = 0;
                    if (Math.random() < 0.5) {
                        num1 = myDeque.peekHead();
                        num2 = testDeque.peekFirst();
                    } else {
                        num1 = myDeque.peekTail();
                        num2 = testDeque.peekLast();
                    }
                    if (num1 != num2) {
                        System.out.println("error4");
                    }
                }
            }
        }
        if (myDeque.size() != testDeque.size()) {
            System.out.println("error5");
        }
        while (!myDeque.isEmpty()) {
            int num1 = myDeque.pollHead();
            int num2 = testDeque.removeFirst();
            if (num1 != num2) {
                System.out.println("error6");
            }
        }
        System.out.println("测试成功！！！");
    }

    public static void main(String[] args) {
        testDeque();
    }
}
